1. Field of the Invention
The present invention is related to a private communication system and more particularly to providing security for a private communication using elliptic curve cryptosystem.
2. Discussion of the Related Art
Cryptographic systems are widely used as the means to provide security during exchange of information. Potentially, the cryptographic systems provide all objectives of information security such as confidentiality, integrity, authentication and availability.
There are two main classes of cryptographic systems, known as a symmetric key system and a public key system. The symmetric key systems have been used for a long time to encrypt and to decrypt messages. In the symmetric key systems, a single key can be used to encrypt and to decrypt messages. While the implementation of the symmetric key system is very efficient, the key management can be troublesome.
On the other hand, since its introduction in 1976, the public key cryptographic system has been studied and used extensively until today. The public key cryptographic systems are used for encryption and decryption, data digital signing and signature verification, and for safe exchange of a secret key through non-secure communication channels. Although public key cryptographic schemes are more convenient for key management, its implementation is currently less efficient than the symmetric key systems.
In a public key encryption scheme, the processes of encryption and decryption are separated. During encryption, a public key, often designated as xe2x80x98exe2x80x99 is employed while a different (but mathematically related) private key xe2x80x98dxe2x80x99 is required for decryption. Knowledge of the public key allows encryption of plaintext but does not allow decryption of the ciphertext without the private key for decryption.
For example, a user selects and publishes a public key. Subsequently, others may use the selected key to encrypt messages for this user. At the same time, a private key corresponding to the public key is kept in secret by the user such that the user is the only one who can decrypt the ciphertext encrypted for the user. Well-known public key cryptographic schemes include RSA, DSA, Diffie-Hellman, ElGamal and elliptic curve cryptosystems (ECC).
A comparison of the public key cryptographic systems shows that the elliptic curve cryptosystems offer the highest strength-per-key-bit among any known systems. With a 162-bit modulus, an elliptic curve system offers the same level of cryptographic security as DSA or RSA having a 1024-bit moduli. Smaller key sizes gives the elliptic curve cryptosystem advantages, including smaller system parameters, smaller public key certificates, bandwidth savings, faster computations, and lower power requirements.
Many cryptosystems require arithmetic to be performed in mathematical structures called a group and a field. A group is a set of elements with a custom-defined arithmetic operation over the elements, while a field is a set of elements with two custom-defined arithmetic operations over its elements. The order of a group is the number of its elements. The arithmetic operations defined in groups and fields requires certain properties, but the properties of a field are more stringent than the properties of a group.
The elliptic curve is an additive group with a basic operation of addition. Elliptic curves as algebraic and geometric entities have been studied extensively for the past 150 years, and from these studies a rich and deep theory had emerged. As a result, the elliptic curve systems as applied to cryptography were proposed in 1985.
Elements of an elliptic curve are pairs of numbers (x, y), called points. The x and y values may be ordinary (real) numbers, or they may be members of a field in which the elliptic curve is defined. Such fields are called the underlying field of the elliptic curve. The choice of the underlying field affects the number of points in the elliptic curve, the speed of elliptic curve computations, and the difficulty of the corresponding discrete logarithm problem. Thus, when elliptic curves are used for cryptosystems, the underlying field affects the key sizes, the computational requirements and the security. Choosing different underlying fields allows an extensive variety of elliptic curves.
Usually two classes of elliptic curve cryptosystems are used, one of which is defined over the underlying field Fp (i.e. modulo prime p) and the other defined over the underlying field F2m (modulo irreducible polynomial of power 2m). The second class of elliptic curve cryptosystems is characterize by considerably less number of suitable curves and has lower performance, except for performance in hardware implementation. Thus, elliptic curve cryptosystem over the underlying field Fp receives more interest. Below, we consider Fp as the underlying field, where p is a prime of a special kind, and an elliptic curve over Fp, defined by equation y2=x3+Ax+B (mod p), where A, B∈Fp. The essential requirement for such elliptic curves is a non-zero curve discriminant, 4A3+27B2xe2x89xa00 (mod p).
The elliptic curve element is an elliptic curve point designated as P(x, y)∈E(Fp). Thus, point P lies on the elliptic curve E defined over underlying field Fp and the point coordinates x, y∈Fp. The order of elliptic curve is the number of points on the elliptic curve. The group operation for an elliptic curve is addition of two elements, i.e. the points. Thus, the basic operation on an elliptic curve is the addition of elliptic curve points. The addition of elliptic curve points results in another point lying on the same elliptic curve. Adding two different points, such as P+Q=R1, is called the addition of two distinguished points. If the same two points are added, i.e. the point is added to itself, such as P+P=2P=R2, the operation is called the doubling of points. A repeated addition of a point with itself is called a scalar multiplication of the point by an integer k: P+P+P+ . . . +P=kP=R3 where k is an integer. The original points and the resulting points all lie on the same elliptic curve: P, Q, R1, R2, R3∈E(Fp).
An order of an elliptic curve point is significant in elliptic curve cryptosystems. The order of elliptic curve point P is the least integer n such that scalar multiplication of point by this number produces a special point on an elliptic curve, called the infinity point O (nP=O). The infinity point is an identity of the elliptic curve as a group.
For the underlying field Fp, if the order of elliptic curve is composite, then the elliptic curve group can be separated into subgroups, and each of the subgroup will have a prime order, i.e. consist of prime number of points. In such case, the order of each subgroup is smaller than the order of elliptic curve. In the subgroup, all points have the same order, which is equal to the order of the subgroup. Group operations over points of one subgroup produce points of the same subgroup again. For example, repeated addition of an arbitrary point of a subgroup with itself produces all the points of the subgroup. By repeating the addition for the number of times equal to the order of the subgroup, the infinity point is produced. The next addition produces the initial point. If the order of an elliptic curve is a prime, the curve cannot be separated into subgroups, and the order of any point would be equal to the order of the elliptic curve.
The following is a list of terms and definitions which will be referred to describe the background art and the present invention.
p: a prime integer;
GF(p): a finite field with p elements, a complete residue system modulo p;
Fp: a brief notation of GF(p);
E: an elliptic curve, defined over Fp by equation y2=x3+Ax+B (mod p);
E(Fp): a group of elements called elliptic curve points, defined over Fp;
#E(Fp): an order of elliptic curve and also a number of points on a curve;
N: another designation of a number of points on an elliptic curve;
n: an order of arbitrary point on elliptic curve, in general case being equal to N;
q: a maximal prime divisor of N, or the prime order of an elliptic curve;
A, B: an arbitrary positive integers, 0xe2x89xa6A, Bxe2x89xa6pxe2x88x921, representing the curve equation coefficients;
Q(x, y): a point on an elliptic curve E(Fp), which satisfy the equation
y2=x3+Ax+B (mod p);
Q(x0,y0): an initial point of an elliptic curve having the order q called group generator;
O: a special point on an elliptic curve E(Fp), called the infinity point;
x, y: x and y coordinates of a point, and arbitrary elements of Fp;
D: complex multiplication (CM) discriminant of E(Fp).
The basis for the security of elliptic curve cryptosystems is the apparent intractability of the elliptic curve discrete logarithm problem (ECDLP) as described below.
Let P∈E(Fp) be a point of order n, and let R∈E(Fp) be another point of E(Fp). Assuming n is known, the elliptic curve logarithm problem is the following: given P and R, determine the unique integer k, 0xe2x89xa6kxe2x89xa6nxe2x88x921, such that R=kP, provided that such integer exists.
The best algorithm known for solving an elliptic curve discrete logarithm problem is the Pollard rho-method, shown in xe2x80x9cMonte Carlo methods for index computations mod pn, xe2x80x9d by J. Pollard, Math. Comp., v. 32, pp. 918-24 (1978). The Pollard rho-method is applicable to any finite group and is an exponential square root attack. Thus, the method has a running time proportional to the square root of the largest prime factor dividing the order of group. Particularly, the method takes approximately {square root over ( )}(xcfx80n/2) steps, where a step is an elliptic curve addition. Also, the Pollard rho-method can be parallelized such that if r processors are used, the expected number of steps necessary by each processor before a single discrete logarithm can be obtained is ({square root over ( )}(xcfx80n/2)/r. Consequently, this root attack may be avoided if an elliptic curve is chosen so that its order is a large prime, or is divisible by a large prime. Currently, the recommended order is 162 bits or higher (for this case, the elliptic curve cryptosystem has a strength roughly equal to 1024-bit RSA).
Hasse""s theorem states that the number of points on an elliptic curve is
#E(Fp)=p+1xc2x1txe2x80x83xe2x80x83(1)
where |t|xe2x89xa6{square root over ( )}p. The exact value depends on prime p and the elliptic curve equation coefficients A and B. In other words, the order of an elliptic curve #E(Fp) is roughly equal to the size p of the underlying field. R. Schoof discloses a polynomial-time algorithm in xe2x80x9cElliptic curves over finite fields and the computation of square roots mod p,xe2x80x9d Mathematics of Computation, v. 44, pp. 483-94 (1985) and R. Lercier and F. Morain discloses an improved algorithm in xe2x80x9cCounting the number of points on elliptic curves over finite fields: strategies and performances,xe2x80x9d Advances in Cryptologyxe2x80x94EUROCRYPT ""95, Lecture Notes in Computer Science, v. 921, pp. 79-94 (1995) for counting the number of points on an elliptic curve.
However, the existing processes and point counting methods, suggested by R. Schoof, R. Lercier and F. Morain, are impractical because of their complexity. Using the current desktop computers may take several days or even weeks for the calculation. A special class of elliptic curves called supersingular exist for which the number of points can be easily computed. However, these supersingular elliptic curves turned out to be disastrous because their discrete logarithm problem can be reduced to a discrete logarithm problem over extensions of underlying field of small degree. See. xe2x80x9cElliptic Curve Public Key Cryptosystemsxe2x80x9d by A. Menezes, Kluwer Academic Publishers, pp. 72-7 (1993). Accordingly, only non-supersingular elliptic curves are used for cryptographic systems.
There are three general approaches to select an elliptic curve for elliptic curve cryptosystems. The three approaches may be summarized as below.
(1) Select a curve at random, compute its order directly, and repeat the process until an appropriate order is found.
(2) Select curve coefficients with particular desired properties, compute the curve order directly, and repeat the process until an appropriate order is found.
(3) Search for an appropriate order, and construct a curve of that order.
The first is a classical approach, but is impractical because it suggests the use of Schoofs or Morain""s point counting algorithm. The second approach depends on the particular desired properties of the cryptosystem. The third approach can be implemented using the complex multiplication (or CM) method. Over GF (p), the CM technique is also called the Atkin-Morain method, described by F. Morain in xe2x80x9cBuilding cyclic elliptic curves modulo large primes,xe2x80x9d Advances in Cryptologyxe2x80x94EUROCRYPT ""91, Lecture Notes in Computer Science, v. 547, pp. 328-36 (1991).
The complex multiplication technique is as follows. If E is a non-supersingular elliptic curve over GF (p) with order n, then Z=4pxe2x88x92(p+1xe2x88x92n)2 where Z is positive by the Hasse bound, see equation (1). Also, there is a unique factorization, Z=DV2 where D is squarefree (i.e. contains no square factors). Accordingly, letting (p+1xe2x88x92n)2=W2, DV2=4pxe2x88x92W2. Thus, for each non-supersingular elliptic curve over GF (p) of order n, there exists a unique squarefree positive integer D such that
4p=W2+DV2,xe2x80x83xe2x80x83(2)
n=p+1xc2x1Wxe2x80x83xe2x80x83(3)
for some W and V.
The non-supersingular elliptic curve E has complex multiplication by D (or, more properly, by {square root over ( )}xe2x88x92D where D is a CM discriminant for p and n. Equation (3), however is for the general case when D greater than 3; therefore,
n=p+1xc2x1W or n=p+1xc2x1V, for D=1xe2x80x83xe2x80x83(3.1)
n=p+1xc2x1W or n=p+1xc2x1(Wxc2x13V)/2, for D=3.xe2x80x83xe2x80x83(3.2)
As a result, four or six different number of points are possible for D=1 and D=3, respectively.
If D is known for a given curve E, its order may be computed via equations (2) and (3). The curve E can be constructed with CM by small D. Therefore one can obtain curves whose orders n satisfy equations (2) and (3.1), and equations (2) and (3.2) for small D.
Special procedure suggests for testing whether a squarefree positive integer D is a CM discriminant for p, and then for producing values W and V satisfying equation (2) to compute the elliptic curve of order n by equation (3). This procedure is recursive and uses the matrix operations. Particularly, the procedure for constructing the elliptic curve with the prescribed CM discriminant D suggests computing reduced symmetric matrices of D, and then computing the reduced class polynomial for D. These algorithms are not time consuming, but are difficult to implement, for any values of D.
Generally, a construction of an elliptic curve cryptosystem includes choosing and computing of its parameters. The set of elliptic curve cryptosystem parameters consists of large prime p, which is a characteristic of the underlying field Fp; elliptic curve coefficients A and B; number of point N and it""s prime divisor q; and initial point Q(x, yo) of order q, called a group generator. The parameters of elliptic curve cryptosystem must satisfy some requirements to provide appropriate security level. These requirements are as follows.
(R1) Elliptic curve must have a non-zero discriminant: 4A3+27B2xe2x89xa00 (mod p).
(R2) Number of points N must have large prime divisor q, or be prime (q=N).
(R3) Number of points N must be relatively prime to prime p.
(R4) The order q must not divide any number from the set {pxe2x88x921, p2xe2x88x921, . . . , pkxe2x88x921}, where k≈log2 (p)/8. This is also called the MOV-condition.
(R5) The group generator Q(x0, y0) must have an order q.
A general process for constructing an elliptic curve cryptosystem is shown in FIG. 1 and comprises the steps of inputting the required ECC bit length n (step S10); generating or choosing a prime p having the required length and constructing the underlying field Fp (step S20); constructing the elliptic curve by choosing equation coefficients A and B for a non-zero discriminant (step S30); computing the number of points N on elliptic curve and its prime divisor q (step S40); checking whether the conditions in requirements (R2)-(R4) are satisfied (step S50); choosing the arbitrary point of elliptic curve as an initial group generator Q(x0, y0) to have order q (step S60); and outputting the ECC parameters (step S70).
However, as discussed above, the available algorithms in the related art to compute the parameters are either time consuming or difficult to implement Therefore, while an elliptic curve cryptosystem may provide information security in communication, a problem of choosing the set of elliptic curve cryptosystem parameters exists.
An object of the present invention is to solve at least the problems and disadvantages of the related art.
An object of the present invention is to provide a process and method for fast construction of an elliptic curve cryptosystem utilized in telecommunication systems.
Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.
The present invention provides according to an embodiment a construction process of a special kind of finite field characteristic p and special types of non-supersingular elliptic curves, where CM discriminant is prescribed. According to the present invention, the number of points and the prime order of elliptic curve are defined by simple equations and can be easily computed. The point counting algorithm has a deterministic character, including a few equations and linear arithmetic operations, namely addition and multiplication.
Also, the present invention provides according to an embodiment a high speed of elliptic curves construction algorithm, including the determining of complete set of cryptosystem parameters, in a few seconds. Moreover, the construction algorithm is flexible such that a new set of cryptosystem parameters can be computed either completely or partially, depending on the actual needs of the telecommunication system. Furthermore, the algorithm does not limit a number of different elliptic curve cryptosystem which can be generated for use in the communication system. Thus, the proposed invention provides a large variety of elliptic curve cryptosystems, which can be easily constructed.